package com.grape.dsaa.lineartable.list.core;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * 描述：链表实现
 * @author: myx
 * @date: 2019-04-28
 * 注意：本内容仅限于学习使用
 * Copyright © 2019-myx. All rights reserved.
 */
public class MyLinkedList<E> implements List<E> {
    private class Node {
        //数据域
        private E data;

        //指针域，指向下一个Node
        private Node next;

        public Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }

        public Node(E data) {
            this(data, null);
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }

    /**
     * 头结点
     */
    private Node head;
    /**
     * 当前list大小
     */
    private int size;

    public MyLinkedList() {
        head = null;
        size = 0;
    }


    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public boolean contains(Object o) {
        Node p = head;
        while(p != null) {
            if(p.data.equals(o)){
                return true;
            }
            p = p.next;
        }
        return false;
    }

    @Override
    public Iterator<E> iterator() {
        return null;
    }

    @Override
    public Object[] toArray() {
        return new Object[0];
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return null;
    }

    @Override
    public boolean add(E e) {
        return false;
    }

    @Override
    public boolean remove(Object o) {
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return false;
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    @Override
    public void clear() {

    }

    @Override
    public E get(int index) {
        if(index<0 || index >= size) {
            throw new IllegalArgumentException("非法下标...");
        }
        Node p = head;
        for(int i=0; i<index; i++){
            p = p.next;
        }
        return p.data;
    }

    @Override
    public E set(int index, E element) {
        if(index<0 || index >= size) {
            throw new IllegalArgumentException("非法下标...");
        }
        Node p = head;
        for(int i=0; i<index; i++){
            p = p.next;
        }
        p.data = element;
        return element;
    }

    @Override
    public void add(int index, E element) {
        if(index < 0 || index > size) {
            throw new IllegalArgumentException("下标越界.....");
        }
        //插到链表头部
        if(index == 0) {
            addFirst(element);
        }else if(index == size) {
            addLast(element);
        }else {
            Node prev = head;
            for(int i=0; i<index; i++) {
                prev = prev.next;
            }
            prev.next = new Node(element, prev.next);
            size++;
        }
    }

    @Override
    public E remove(int index) {
        if(index<0 || index >= size) {
            throw new IllegalArgumentException("非法下标...");
        }
        if(index == 0) {
            return removeFirst();
        }else if (index == size -1) {
            return removeLast();
        }else{
            Node prev = head;
            for(int i=0; i<index-1; i++){
                prev = prev.next;
            }
            Node tmp = prev.next;
            prev.next = tmp.next;
            tmp.next = null;
            size--;
            return tmp.data;
        }
    }

    @Override
    public int indexOf(Object o) {
        int result = -1;
        Node p = head;
        int i = 0;
        while(p != null) {
            if(p.data.equals(o)){
                result = i;
                break;
            }
            p = p.next;
            i++;
        }
        return result;
    }

    @Override
    public int lastIndexOf(Object o) {
        return 0;
    }

    @Override
    public ListIterator<E> listIterator() {
        return null;
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        return null;
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        return null;
    }




    public void addFirst(E e) {
        Node node = new Node(e, head);
        head = node;
        size++;
    }

    public void addLast(E e) {
        Node node = new Node(e, null);
        //链表为空
        if(head == null) {
            head = node;
        }else {
            Node prev = head;
            while(prev.next != null) {
                prev = prev.next;
            }
            prev.next = node;
        }
        size++;
    }
    public E removeFirst() {
        if(head == null){
            return null;
        }
        E result = head.data;
        head = head.next;
        size--;
        return result;
    }

    public E removeLast() {
        if(head == null){
            return null;
        }
        E result;
        //链表只有一个节点
        if(head.next == null) {
            result = head.data;
            head = null;
        }else {
            Node prev = head;
            while(prev.next.next != null){
                prev = prev.next;
            }
            result = prev.next.data;
            prev.next = null;
        }
        size--;
        return result;
    }
}
